package leetCode;

import cn.hutool.core.lang.Console;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class ErChaShuZhongHeWeiMouYiZhiDeLu68dg {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Console.log(getResult(root, 38));
    }

    private static List<List<Integer>> getResult(TreeNode root, int target){
        List<List<Integer>> ret = new LinkedList<>();
        Deque<Integer> path = new LinkedList<>();

        dfs(root, target, ret, path);
        return ret;
    }

    private static void dfs(TreeNode root, int target, List<List<Integer>> ret, Deque<Integer> path) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        target -= root.val;
        if (root.left == null && root.right == null && target == 0) {
            ret.add(new LinkedList<>(path));
        }
        dfs(root.left, target, ret, path);
        dfs(root.right, target, ret, path);
        path.pollLast();
    }
}
